package q216

func combinationSum3(k int, n int) [][]int {
	return combinationSum3Recursive(k, n, 1)
}

func combinationSum3Recursive(k, n int, min int) [][]int {
	ret := [][]int{}
	if n == 0 && k == 0 {
		ret = append(ret, []int{})
		return ret
	} else if n < 0 || k < 0 {
		return ret
	}

	if k == 1 && n <= 9 && n >= min {
		ret = append(ret, []int{n})
		return ret
	}

	for i := min; i <= 9 && i <= n; i++ {

		val := i
		combina := combinationSum3Recursive(k-1, n-val, i+1)
		for _, v := range combina {
			if len(v) != (k - 1) {
				continue
			}
			t := append(v, val)
			ret = append(ret, t)
		}
	}

	return ret
}
